package easy;

public class T35 {
    public static void main(String[] args) {
        System.out.println(searchInsert(new int[] {1, 3, 5, 6}, 7));
    }
    public static int searchInsert(int[] nums, int target) {
        return find(nums, target, 0, nums.length - 1);
    }

    // 二分查找
    public static int find(int[] nums, int target, int left, int right) {
        if (left == right){
            if (target == nums[left]) {
                return left;
            }else {
                if (nums[left] > target){
                    return left - 1;
                }else {
                    return left+1;
                }
            }
        }
        int mid = (right + left) / 2;
        if (target == nums[mid]) {
            return mid;
        } else if (target < nums[mid]) {
            return find(nums, target, left, mid);
        } else {
            return find(nums, target, mid + 1, right);
        }
    }
}
